package test;

/**
 * @author : RobertWei
 * time: 2021/9/27    11:04
 * description:
 */

public class Demo {

    public static void main(String[] args) {

        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(5);
        ListNode l2 = new ListNode(4);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);
        l2.next.next.next = new ListNode(7);

        ListNode merge = mergeTwoList(l1, l2);

        while (merge != null) {
            System.out.print(merge.val + " ");
            merge=merge.next;
        }

    }

    public static ListNode mergeTwoList(ListNode l1 , ListNode l2) {

        //如果有一个链表为空 直接返回 另一个链表
        if (l1 == null ) {
            return l2;
        }

        if (l2 == null ) {
            return l1;
        }

        //创建需要返回的头链表
        ListNode head;

        //创建每个链表的下一个节点
        ListNode n1 = l1.next;
        ListNode n2 = l2.next;

        //设置头节点的值
        if (l1.val < l2.val){
            head = l1;
        }else {
            head = l2;
        }

        //创建随 循环移动的可移动节点
        ListNode move = head;

        //
        while (true){

            if (l1.val < l2.val) {
                //当l1 链表的 n1 不为null  并且 n1 的值 小于 l2 的值, 则将move的下一个设置为n1
                while (n1 != null && n1.val < l2.val ) {

                    move.next = n1;
                    move = move.next;
                    l1 = n1;
                    n1 = n1.next;

                }

                //将move 的下一个值设置为l2 并移动
                move.next = l2;
                move = move.next;

                //如果n1 为空则证明完成循环 , 直接跳出循环
                if (n1 == null){
                    break;
                }

                //如果n2 位null 则将move之后内容设置为 n1 跳出循环
                if (n2 == null ){
                    move.next = n1;
                    break;
                }

                l2 = n2;
                n2 = n2.next;

            }else {
                //当l2 链表的 n2 不为null  并且 n2 的值 小于 l1 的值, 则将move的下一个设置为n2
                while (n2 != null && n2.val < l1.val) {

                    move.next = n2;
                    move = move.next;
                    l2 = n2;
                    n2 = n2.next;
                }

                //将move 的下一个值设置为l1 并移动
                move.next = l1;
                move = move.next;

                //如果n1 为空则证明完成循环 , 直接跳出循环
                if (n2 == null){
                    break;
                }

                //如果n2 位null 则将move之后内容设置为 n1 跳出循环
                if (n1 == null ){
                    move.next = n2;
                    break;
                }

                l1 = n1;
                n1 = n1.next;
            }

        }

        return head;

    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
